<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <!-- <script>
    var exist = function (board, word) {
      const [m, n, l] = [board.length, board[0].length, word.length];
      if (m * n < l) return false; // 矩阵过小
      function dfs(i, j, index) {
        if (i < 0 || i >= m || j < 0 || j >= n || word[index] != board[i][j]) return false;
        if (index === l - 1) return true;
        let tmp = board[i][j];
        board[i][j] = null;
        let res = dfs(i - 1, j, index + 1) ||
          dfs(i + 1, j, index + 1) ||
          dfs(i, j + 1, index + 1) ||
          dfs(i, j - 1, index + 1);
        board[i][j] = tmp;
        return res;
      }

      for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
          if (dfs(i, j, 0)) return true;
        }
      }
      return false;
    };
    
  </script> -->
  <script>
    var exist = function (board, word) {
      let row = board.length;
      let col = board[0].length;
      // 防止边界超出
      board[-1] = [];
      board.push([]);

      let dfs = (board, word, i, x, y) => {
        if (i + 1 === word.length) return true;
        let temp = board[x][y];
        board[x][y] = false;
        if (word[i + 1] === board[x][y - 1] && dfs(board, word, i + 1, x, y - 1)) return true;
        if (word[i + 1] === board[x][y + 1] && dfs(board, word, i + 1, x, y + 1)) return true;
        if (word[i + 1] === board[x - 1][y] && dfs(board, word, i + 1, x - 1, y)) return true;
        if (word[i + 1] === board[x + 1][y] && dfs(board, word, i + 1, x + 1, y)) return true;
        board[x][y] = temp;
        return false;
      }

      for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
          if (board[i][j] === word[0] && dfs(board, word, 0, i, j)) return true;
        }
      }
      return false
    };
    console.log(exist(board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"));
  </script>
</body>

</html>